'''
希尔排序是一种分组插入排序算法
首先取一个整数d1 = n/2,将元素分为d1个组,每组相邻量元素之间距离为d1
,在各组内直接插入排序
取第二个整数d2 = d1/2,重复上述分组排序过程,直到d1 = 1,即所有元素在同一组内直接进行插入排序
希尔排序没糖并不使某些元素有序,而是使整体数据越来越接近有序,最后一趟排序使得所有数据有序
'''
def insert_sort_gap(li,gap):
    n = len(li)
    for i in range(gap,n):
        tmp = li[i]
        j = i - gap
        while j >= 0 and li[j] > tmp:
            li[j+gap] = li[j]
            j -= gap
        li[j+gap] = tmp

def shell_sort(li):
    d = len(li)//2
    while d >= 1:
        insert_sort_gap(li,d)
        d //= 2

li = list(range(1000))
import random
random.shuffle(li)
shell_sort(li)
print(li)


